package demo.letcode.top100;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class _滑动窗口 {
    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 4, 1};
        int k = 3;
//        m1(arr, k);
        m2(arr, k);
    }

    private static void m2(int[] arr, int k) {
        // 计算滑动窗口最大和

    }

    private static void m1(int[] arr, int k) {
        // 寻找窗口中最大的值
        Deque<Integer> deque = new ArrayDeque<>();
        // 保证最大的在队首
        int[] ans = new int[arr.length - k + 1];
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        ans[0] = arr[deque.peekFirst()];
        for (int i = k; i < arr.length; i++) {
            while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // i=3移除<=0 i-k
            // i=4移除<=1 4-3
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = arr[deque.peekFirst()];
        }
        System.out.println(Arrays.toString(ans));
    }
}
